In parallel computer systems that are information processing systems, barrier synchronization is known as a method for synchronizing multiple processes performed, in parallel processing, by multiple nodes. In the barrier synchronization, a synchronization point in which synchronization is performed is set in accordance with stages of progress of a process. In a process that performs the barrier synchronization, if a process performed by a node reaches the synchronization point, the node waits, by temporarily stopping the process, for the progress of the processes performed by other nodes. The process that performs the barrier synchronization ends its waiting state when all of the processes that perform the barrier synchronization in parallel processing reaches the synchronization point and then restarts the stopped process. Consequently, it is possible to synchronize the parallel processing between multiple processes that are performed among the multiple nodes.
There is a conventional technology in which, for example, in a barrier synchronization device, a combination of two nodes repeatedly exchange messages and check whether all nodes reach a synchronization point. For example, two nodes are grouped into a single group and, when the sending and receiving of data have been completed between these two nodes, it is determined that these two nodes in the same group reach the synchronization point. Thereafter, when a specific node in each group was able to send and receive data to and from a specific node in the subsequent group, it is determined that the process reaches a synchronization point with respect to the counterpart group. Then, this process is repeatedly performed until all of the nodes reach the synchronization point.
When the barrier synchronization is performed in this way, the time taken to perform the barrier synchronization is proportional to log2N, where the number of nodes is N.    Patent Document 1: Japanese Laid-open Patent Publication No. 07-152712
However, in the conventional technology in which synchronization is repeatedly performed by using two nodes as a group, because the ratio of the time taken for the barrier synchronization to the time taken for overall process increases as the number of nodes increase, the barrier synchronization is a bottleneck in the process. In particular, some supercomputers used in recent years include thousands to tens of thousands of nodes and, furthermore, the number of nodes tends to be increased; therefore, the time taken for the barrier synchronization is being increased.